// 两个栈实现一个队列
var CQueue = function () {
    this.stack1 = [];
    this.stack2 = [];

};

CQueue.prototype.appendTail = function (value) {
    this.stack1.push(value);
};

CQueue.prototype.deleteHead = function () {
    // 必须等stack2中没有了元素才能遍历stack1向stack2添加元素（关键）
    if (this.stack2.length) {
        return this.stack2.pop();
    } else {
        while (this.stack1.length) {
            this.stack2.push(this.stack1.pop());
        }
        if (!this.stack2.length) {
            return -1;
        } else {
            return this.stack2.pop();
        }
    }
};


//  斐波那契/爬楼梯问题
// 1.递归 时间复杂度 O(2^n)
var fib = function (n) {
    if (n < 2) {
        return n;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
};
// 2.备忘录 时间复杂度O(n) 空间复杂度O(n)
var fib = function (n) {
    if (n < 2) {
        return n;
    }
    var res = [0, 1];
    for (let i = 2; i <= n; i++) {
        res[i] = res[i - 1] + res[i - 2];
    }
    return res[n]
};
// 3.动态规划 时间复杂度O(n) 空间复杂度O(1)
var fib = function (n) {
    if (n < 2) {
        return n;
    }
    var p = 0; q = 0; r = 1;
    for (let i = 2; i <= n; i++) {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
};

// 链表的倒数第K个节点 
// 1.快慢指针 时间复杂度O(n) 空间复杂度O(1)
var getKthFromEnd = function (head, k) {
    let fast = head
    let slow = head
    let n = 0
    while (fast) {
        if (n >= k) slow = slow.next
        fast = fast.next
        n += 1
    }
    return slow;
};

// 二进制中1的个数
// 1.利用逻辑与&  1&0=0 0&0=0 1&1=1
var hammingWeight = function (n) {
    let count = 0;
    while (n !== 0) {
        console.log(n.toString(2));
        n = n & (n - 1);
        count++;
    }
    return count;
};
var res = hammingWeight(10);
console.log(res);

var hammingWeight = function (n) {
    let count = 0
    for (let i = 0; i < 32; i++) {
        if ((n >> i) & 1) {
            count++
        }
    }
    return count
};


// 合并两个排序链表
var mergeTwoLists = function (l1, l2) {
    var head = new ListNode();
    var h = head;
    while (l1 && l2) {
        if (l1.val < l2.val) {
            head.next = l1;
            l1 = l1.next;
        } else {
            head.next = l2;
            l2 = l2.next;
        }
        head = head.next;
    }
    if (l1) head.next = l1;
    if (l2) head.next = l2;
    return h.next
};

// 反转链表....
const reverseList = function (head) {
    let prev = null;
    let curr = head;
    while (curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// 二叉树的所有路径
var binaryTreePaths = function (root) {
    const paths = [];
    const construct_paths = (root, path) => {
        if (root) {
            path += root.val.toString();
            if (root.left === null && root.right === null) { // 当前节点是叶子节点
                paths.push(path); // 把路径加入到答案中
            } else {
                path += "->"; // 当前节点不是叶子节点，继续递归遍历
                construct_paths(root.left, path);
                construct_paths(root.right, path);
            }
        }
    }
    construct_paths(root, "");
    return paths;
};

// 最大连续子数组和
var maxSubArray = function (nums) {
    let pre = cur = sum = nums[0]; //cur和sum没用let声明，都无所谓的
    // let cur = nums[0];
    // let sum = nums[0]
    for (let i = 1; i < nums.length; i++) {
        cur = pre >= 0 ? pre + nums[i] : nums[i];
        pre = cur;
        sum = sum > pre ? sum : pre
    }
    return sum
};
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));

// 最长无重复字串长度
var lengthOfLongestSubstring = function (s) {
    let a = {};
    let l = 0;
    let r = 0;
    let max = 0;
    let len = s.length;
    while (l < len && r < len) {
        if (!a[s[r]]) {
            a[s[r]] = 1;
            r++;
        } else {
            a[s[l]] = 0;
            l++;
        }
        max = Math.max(max, (r - l));
    }
    return max;
};

// 比较版本号
var compareVersion = function (version1, version2) {
    version1 = version1.split('.');
    version2 = version2.split('.');
    let n = Math.max(version1.length, version2.length)
    for (let i = 0; i < n; i++) {
        let code1 = (version1[i] === undefined) ? 0 : parseInt(version1[i]);
        let code2 = (version2[i] === undefined) ? 0 : parseInt(version2[i]);
        if (code1 > code2) {
            return 1
        } else if (code1 < code2) {
            return -1;
        }
    }
    return 0
};

// 全排列(回溯法)
var permute = function (nums) {
    const res = [];
    const used = {};

    function dfs(path) {
        console.log(path);
        if (path.length == nums.length) { // 个数选够了
            res.push(path.slice()); // 拷贝一份path，加入解集res
            return;                 // 结束当前递归分支
        }
        for (const num of nums) { // for枚举出每个可选的选项
            // if (path.includes(num)) continue; // 别这么写！查找的时间是O(n)，增加时间复杂度
            if (used[num]) continue; // 使用过的，跳过
            path.push(num);         // 选择当前的数，加入path
            used[num] = true;       // 记录一下 使用了
            dfs(path);              // 基于选了当前的数，递归
            path.pop();             // 上一句的递归结束，回溯，将最后选的数pop出来
            used[num] = false;      // 撤销这个记录
        }
    }

    dfs([]); // 递归的入口，空path传进去
    return res;
};
console.log(permute([1, 2, 3]));

// LRU缓存机制
/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    this.map = new Map();
    this.count = capacity;
};
/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    if (this.map.has(key)) {
        var temp = this.map.get(key)
        this.map.delete(key)
        this.map.set(key, temp)
        return temp
    } else {
        return -1
    }
};
/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    if (this.map.size < this.count & !this.map.has(key)) {
        this.map.set(key, value);
    } else if (this.map.has(key)) {
        this.map.delete(key);
        this.map.set(key, value);
    } else if (this.map.size === this.count) {
        this.map.delete(this.map.keys().next().value)
        this.map.set(key, value)
    }
};



